
// 给定一个整数数组和一个整数 k，请设计算法找到该数组中和为 k 的连续的子数组的个数。

var subarraySum: (nums: number[], k: number) => number = function (nums, k) {
    // 定义哈希表=>key：前缀和值 value：前缀和出现的个数
    const hashMap = new Map<number, number>();
    // 初始化计数变量，前缀和变量，哈希表（表示前缀和为0的元素有1个，因为默认不选前缀和就为0）
    hashMap.set(0, 1);
    let count: number = 0;
    let currSum: number = 0;
    // 循环部分
    for (let num of nums) {
        // 前缀和更新
        currSum = currSum + num;
        // 重要：当计算完包括了当前数前缀和以后，去查在当前数之前，有多少前缀和等于 currSum - k
        if (hashMap.has(currSum - k)) {
            // 如果哈希表中存在，计数变量直接加上满足情况前缀和的个数
            count += <number>hashMap.get(currSum - k);
        }
        // 默认操作：维护哈希表
        let currCount: number = hashMap.get(currSum) || 0;
        hashMap.set(currSum, currCount + 1);
    }
    // 返回计数变量
    return count;
};
        // 这道题的最优解法不好想，它是基于前缀和数组的解法优化来的
        // 思想是利用一个哈希表来代替前缀和数组
        // 哈希表的key是表示前缀和为X的元素
        // value则表示前缀和为X的元素有多少个
        // 可以这么代替的原因是因为我们不关心这个子数组具体的结构而只关心子数组的个数
        // 我们每次计算完包括了当前数的前缀和以后，需要去查一查在当前数之前，有多少个前缀和等于 currSum - k 呢
        // 这里可以联想：例如 k = 3,当我们遍历到[1,-1,3...]时和[1,-1,3,-3,3...]的情况，前者的0=>2,后者的0->3
        // 所以在每轮循环里，我们不断地维护这个哈希表，然后去哈希表中查询是否存在（k-当前前缀和）变量
        // 如果存在，那么直接为计数变量加上哈希表的value
        // 循环结束后返回计数变量即可
